{
 "metadata": {
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.6-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2,
 "cells": [
  {
   "source": [
    "# 归并排序"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "对我而言是无法理解的一个排序算法。"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "最好，最坏，评价时间复杂度都是  O(nlogn)\n",
    "\n",
    "空间复杂度是  O(n)"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "![](https://pic1.zhimg.com/80/v2-20b31e4e496bf18f1121824f8b6476d0_720w.jpg)"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge(L, R):\n",
    "    \"\"\"\n",
    "    功能：排序合并\n",
    "    问题来了，如何把两个排好序的数组合并到一起。\n",
    "    可以使用双指针\n",
    "    \"\"\"\n",
    "    n = len(L) + len(R)\n",
    "    arr = []\n",
    "    L.append(float('inf'))\n",
    "    R.append(float('inf'))\n",
    "    i = 0\n",
    "    j = 0\n",
    "    for _ in range(n):\n",
    "        if L[i] <= R[j]:\n",
    "            arr.append(L[i])\n",
    "            i = i+1\n",
    "        else:\n",
    "            arr.append(R[j])\n",
    "            j = j +1\n",
    "    return arr\n",
    "\n",
    "\n",
    "\n",
    "def merge_sort(A):\n",
    "    \"\"\"\n",
    "    函数主体，做过递归题的想到这步并不是太难。\n",
    "    有点像leetcode上有序链表转二叉搜索树的题\n",
    "    主函数的逻辑主要就是拆分数组，拆分成上面第4层的样子\n",
    "    \"\"\"\n",
    "    l = len(A)\n",
    "    if l <= 1:\n",
    "        return A\n",
    "    else:\n",
    "        mid = l // 2\n",
    "        left = merge_sort(A[:mid])\n",
    "        right = merge_sort(A[mid:])\n",
    "        return merge(left, right)\n",
    "# https://zhuanlan.zhihu.com/p/32071231\n",
    "# https://www.runoob.com/python3/python-merge-sort.html"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "[2, 3, 5, 5, 11, 23, 45, 213, 1234]"
      ]
     },
     "metadata": {},
     "execution_count": 2
    }
   ],
   "source": [
    "merge_sort([3,5,5,23,213,1234,45,2,11])"
   ]
  }
 ]
}